import java.util.Scanner;

/**
 *01背包模板
 * https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
 */

class t{
    static int N = 1010;
    static int dp[][] = new int[N][N];

    static int v[] = new int[N];
    static int w[] = new int[N];

    static int n, V;

    public static void main(String[] args) {
        Scanner in  = new Scanner(System.in);
        n = in.nextInt(); V = in.nextInt();

        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V]);

//问题二：改变初始化的表

        for (int j = 1; j <= V; j++) dp[0][j] = -1;

        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= 1; j--) {
                dp[i][j] = dp[i -1][j];
                if (j >= v[i] && dp[i - 1][j - v[i]] != -1)
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }

        System.out.println((dp[n][V] == -1 ? 0 : dp[n][V]));
    }
}